package backtrack

import "sort"

func combinationSum(candidates []int, target int) [][]int {
	res := [][]int{}
	path := []int{}
	sum := 0
	sort.Ints(candidates)
	var backtrack func(int)
	backtrack = func(start int) {
		if sum == target {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
			return 
		}
		if sum > target {
			return 
		}
		for i := start; i < len(candidates); i++ {
			sum += candidates[i]
			path = append(path, candidates[i])
			backtrack(i)
			sum -= candidates[i]
			path = path[:len(path)-1]
		}
	}
	backtrack(0)
	return res
}